package arithmetic;


import utils.PrintUtil;

import java.util.*;

/**
 * @Author: Jie
 * @Date: 2019/2/18 17:31
 * @Function :51 N皇后问题
 * https://leetcode-cn.com/problems/n-queens
 * 思路：
 * 1.循环遍历所有的位置
 * 2.验证位置的合法性。
 * 3.怎么验证：
 *     1.横、竖、斜线2调 45度 x+y=n, x-y=m
 *
 */
public class A_16_NQueens {
    public static void main(String[] args) {
        List<String> a=new ArrayList<>();
        a.add(0,"111");
        a.add(0,"111");
        a.add(0,"111");
        PrintUtil.print(a);

        PrintUtil.print(solveNQueens(4));
//        PrintUtil.printStr(solve(4));
    }

    /**
     * 思路：
     * 行、列、撇、捺、
     * 行 y  n+1
     * 列 x缓存 set
     * 撇 x-y=c
     * 捺 x+y=q
     *
     * @param n
     * @return
     */
    public static List<List<String>> solveNQueens(int n) {
        ArrayList<List<String>> lists = new ArrayList<>();
        HashSet<Integer> col = new HashSet<>();
        HashSet<Integer> pie = new HashSet<>();
        HashSet<Integer> na = new HashSet<>();
        ArrayList<String> strList = new ArrayList<>();
        getBack(lists, strList,n, 0, col, pie, na);
        return lists;
    }
    /**
     * 执行用时: 29 ms, 在N-Queens的Java提交中击败了10.67% 的用户
     * 内存消耗: 36.8 MB, 在N-Queens的Java提交中击败了9.30% 的用户
     * @param resultLists
     * @param currentStrList
     * @param n
     * @param y
     * @param col
     * @param pie
     * @param na
     */
    private static void getBack(ArrayList<List<String>> resultLists, ArrayList<String> currentStrList, int n, int y, HashSet<Integer> col, HashSet<Integer> pie, HashSet<Integer> na) {
        if (y == n) {
            currentStrList= (ArrayList<String>) currentStrList.clone();
            resultLists.add(currentStrList);
            return;
        }
        for (int x = 0; x < n; x++) {
            if (col.contains(x) || pie.contains(x - y) || na.contains(x + y)) {
              continue;
            }

            //此位置,通过了校验，可能存在解。进行下一步
            char[] row = new char[n];
            for (int i = 0, len = row.length; i < len; i++){
                row[i] = '.';
            }
            row [ x ] = 'Q';


            if (currentStrList.size()>=y+1){
                currentStrList.set(y,new String(row));//覆盖之前的值. set
                System.out.println("set..."+y);
            }else {
                currentStrList.add(y,new String(row));//如果没有当前行。add
            }
            //此行通过校验，进行下一行前，加入限制条件。
            col.add(x);
            pie.add(x-y);
            na.add(x+y);

            //进行下一行。递归。
            getBack(resultLists,currentStrList,n,y+1,col,pie,na);

            //此行递归到最后，回退。通过了，或者没通过都可以。
            //删除限制条件。测试 for 循环中 row x 的另一个位置。
            //因为col，pie，na，多次循环，递归这些层，都是调用的同一个 集合、地址。
            col.remove(x);
            pie.remove(x-y);
            na.remove(x+y);
        }
    }


    //方法 2，用 数组替换集合
    public static List<String[]> solve(int n){
        ArrayList<String[]> res = new ArrayList<>();
        boolean [] col = new boolean[n];
        boolean [] pie = new boolean[2*n];
        boolean [] na = new boolean[2*n];
        String[] map = new String[n];
        System.out.println(map.length+"----");
        getbackTwo(res,map,n,0,col,pie,na);
        return res;
    }
    private static void getbackTwo(ArrayList<String[]> res, String[] map, int n, int row, boolean[] col, boolean[] pie, boolean[] na) {
        if (row == n){
//            res.add(map); TODO
            res.add(map.clone());//因为回溯 替换之间的解会 操作同一地址的数组 进而改变结果。
            return;
        }
        for (int x = 0; x < n; x++) {
            if (!col[x]&&!pie[x-row+n] &&!na[n*2 - x - row - 1]){
                char[] r = new char[n];
                Arrays.fill(r,'.');
                r [ x ] = 'Q';
                map[row] = new String(r);
                col[x] = true;
                pie[x-row+n] = true;
                na[n*2 - x - row -1] = true;
                getbackTwo(res,map, n, row+1,col,pie,na);
                //回溯
                col[x] = false;
                pie[x-row+n] = false;
                na[n*2 - x - row -1] = false;
            }
        }
    }

}
